package cn.xkai.exercise.a;

import com.google.gson.Gson;

import java.util.Arrays;

/**
 * @description: 合并两个有序数组
 * 自己的思路：
 * 暴力法：直接把nums2追加到nums1空白为主进行升序排列;
 * 双指针：把nums2依次与nums1比较然后做交换，中间需要把nums2重新排序;
 * 新数组：依次比较nums1和nums2的值放到新数组，然后把新数组的值赋值给nums1;
 * 借鉴的思路：新数组、从后往前比较
 * @author: kaixiang
 * @date: 2022-07-12
 **/
public class Solution48 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n <= 0) {
            return;
        }
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
    }

    public void mergePoints(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        int left = 0, right = 0;
        while (left < m + n) {
            if (left >= m && nums1[left] == 0) {
                nums1[left] = nums2[right];
                left++;
                right++;
                continue;
            }
            if (nums1[left] <= nums2[right]) {
                left++;
                continue;
            }
            nums1[left] = nums1[left] ^ nums2[right];
            nums2[right] = nums1[left] ^ nums2[right];
            nums1[left] = nums1[left] ^ nums2[right];
            int temp = right;
            while (temp < n) {
                if (temp + 1 < n && nums2[temp] > nums2[temp + 1]) {
                    nums2[temp] = nums2[temp] ^ nums2[temp + 1];
                    nums2[temp + 1] = nums2[temp] ^ nums2[temp + 1];
                    nums2[temp] = nums2[temp] ^ nums2[temp + 1];
                }
                temp++;
            }
            left++;
        }
    }

    public void mergeArray(int[] nums1, int m, int[] nums2, int n) {
        int[] nums = new int[m + n];
        int p1 = 0, p2 = 0, index = 0;
        while (p1 != m || p2 != n) {
            if (p1 == m) {
                nums[index++] = nums2[p2];
                p2++;
                continue;
            }
            if (p2 == n) {
                nums[index++] = nums1[p1];
                p1++;
                continue;
            }
            if (nums1[p1] <= nums2[p2] && p1 < m) {
                nums[index++] = nums1[p1];
                p1++;
            } else {
                nums[index++] = nums2[p2];
                p2++;
            }
        }
        System.arraycopy(nums, 0, nums1, 0, nums.length);
    }

    public void mergeArrayRefer(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        int index = 0;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                temp[index++] = nums1[i++];
            } else {
                temp[index++] = nums2[j++];
            }
        }
        while (i < m) {
            temp[index++] = nums1[i++];
        }
        while (j < n) {
            temp[index++] = nums2[j++];
        }
        //再把数组temp中的值赋给nums1
        if (m + n >= 0) {
            System.arraycopy(temp, 0, nums1, 0, m + n);
        }
    }

    public void mergeReduce(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int end = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[end--] = nums1[i--];
            } else {
                nums1[end--] = nums2[j--];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {4, 5, 6, 0, 0, 0};
        int[] nums2 = {1, 2, 3};
        int m = 3;
        int n = 3;
        Solution48 solution48 = new Solution48();
        solution48.mergeArrayRefer(nums1, m, nums2, n);
        System.out.println(new Gson().toJson(nums1));
    }
}
